package com.example.javamaday.leetcode;

public class LeetCodeTest0204 {

    public static void main(String[] args) {

    }

    public int countPrimes(int n) {
        if (n - 1 < 2) {
            return 0;
        }
        if (n - 1 == 2) {
            return 1;
        }
        int num = 0;
        int[] temp = new int[n];
        for (int i = 0; i < n; i++) {
            temp[i] = 1;
        }
        temp[0] = 0;
        temp[1] = 0;
        for (int i = 2; i < n; i++) {
            if (i == 2) {
                temp[i] = 1;
                for (int j = 2; j * i < n; j++) {
                    temp[i * j] = 0;
                }
                continue;
            }
            if (i == 3) {
                temp[i] = 1;
                for (int j = 2; j * i < n; j++) {
                    temp[i * j] = 0;
                }
                continue;
            }
            if (temp[i] == 1) {
                for (int j = 2; j * i < n; j++) {
                    temp[i * j] = 0;
                }
                continue;
            }
        }
        for (int i = 0; i < n; i++) {
            if (temp[i] == 1) {
                num++;
            }
        }
        return num;
    }


    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        long[] result = new long[n];
        result[0] = 0;
        result[1] = 1;
        for(int i = 2; i < n-1; i++) {
            result[i] = result[i-1] + result[i-2];
            System.out.println(result[i]);
        }
        return (int) (result[n-1] % 1000000007);
    }
}
